package com.licw.templates.SegmentTree;


/**
 * 基础版线段树（只支持单点修改和区间查询）
 */
public class SegmentTree0 {
    private final int[] sum;
    private final int maxV;

    public SegmentTree0(int maxV) {
        this.maxV = maxV;
        // 设置为4 * n也行, 下面写法更节省内存
        int sz = 2 << (32 - Integer.numberOfLeadingZeros(maxV));
        this.sum = new int[sz];
    }

    /**
     * 给idx位置 +val
     */
    public void add(int idx, int val) {
        this.add(1, 1, maxV, idx, val);
    }

    /**
     * 查询[l, r]区间和
     */
    public int query(int ql, int qr) {
        return this.query(1, 1, maxV, ql, qr);
    }


    /**
     * @param nodeId 当前节点id, 范围[l, r]
     * @param l      当前节点左边界
     * @param r      当前节点右边界
     * @param idx    修改的下标
     * @param val    修改（增加）值
     */
    private void add(int nodeId, int l, int r, int idx, int val) {
        // 叶子节点
        if (l == r) {
            sum[nodeId] += val;
            return;
        }
        int m = l + (r - l) / 2;
        if (idx <= m) {
            // 左子树
            add(nodeId * 2, l, m, idx, val);
        } else {
            //右子树
            add(nodeId * 2 + 1, m + 1, r, idx, val);
        }
        sum[nodeId] = sum[nodeId * 2] + sum[nodeId * 2 + 1];
    }


    /**
     * 查询区间[qL, qR] 的结果
     *
     * @param nodeId 当前节点id, 范围[l, r]
     * @param l      当前节点左边界
     * @param r      当前节点右边界
     * @param qL     查询区间左边界
     * @param qR     查询区间右边界
     */
    private int query(int nodeId, int l, int r, int qL, int qR) {
        // 如果节点区间位于查询区间之内，直接返回该区间的值
        if (qL <= l && qR >= r) {
            return sum[nodeId];
        }
        int res = 0;
        int m = l + (r - l) / 2;
        if (qL <= m) {
            // 左子树包含部分查询区间
            res += query(nodeId * 2, l, m, qL, qR);
        }
        if (qR > m) {
            // 左子树包含部分查询区间
            res += query(nodeId * 2 + 1, m + 1, r, qL, qR);
        }
        return res;
    }

}